import java.util.*;

class Solution06 {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 准备工作
        // 创建邻接表
        Map<Integer, List<Integer>> edges = new HashMap<>();
        // 用一个数组记录入度是多少
        int[] in = new int[numCourses];
        // 建图
        int m = prerequisites.length;
        for (int i = 0; i < m; i++) {
            // 拿到两个学习课程
            int a = prerequisites[i][0], b = prerequisites[i][1];
            // b ---> a
            // 进行判断
            if (!edges.containsKey(b)) {
                edges.put(b, new ArrayList<>());
            }
            edges.get(b).add(a);
            // 计算入度
            in[a]++;
        }
        // 在图中进行拓扑排序
        Queue<Integer> q = new LinkedList<>();
        // 先把入度为0的点加入到队列里面
        for (int i = 0; i < numCourses; i++) {
            // 进行判断
            if (in[i] == 0) {
                q.add(i);
            }
        }
        // 队列不为空，进行循环判断
        while (!q.isEmpty()) {
            // 拿出队头元素
            int t = q.poll();
            // 删除该点相连的所有边，让该点相连的点入度为1
            for (int x : edges.getOrDefault(t, new ArrayList<>())) {
                in[x]--;
                // 进行判断，如果入度为0，则可以加入队列
                if (in[x] == 0) {
                    // 加入队列
                    q.add(x);
                }
            }
        }
        // 判断是否有环,看入度数组
        for (int x : in) {
            if (x != 0) {
                return false;
            }
        }
        return true;
    }
}